package lt.vu.spf.graph;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;

/**
 * @author Mantas Sinkevičius
 */
public class Graph implements Serializable {
    private static final long serialVersionUID = 177433140378446793L;

    private List<Vertex> vertices = new ArrayList<Vertex>();
    private List<Edge> edges = new ArrayList<Edge>();
    private HashMap<Vertex, Vertex> predecessors;
    private Vertex startingVertex;
    private Vertex destinationVertex;
    private Vertex selectedVertex;
    private Edge selectedEdge;

    /**
     * Pridedama viršūnė, jei tokia pati neagzistuoja ir jei nepersikerta su kitomis viršūnėmis
     */
    public void addVertex(Vertex vertex) {
        if (!vertices.contains(vertex)) {
            vertices.add(vertex);
        }
        findShortestPath();
    }

    /**
     * Ištrinama pasirinkta viršūnė.
     */
    public void removeSelectedVertex() {
        removeVertex(selectedVertex);
        selectedVertex = null;
    }

    /**
     * Ištrinama nurodyta viršūnė ir visos jos briaunos.
     * @param vertex trinama viršūnė
     */
    private void removeVertex(Vertex vertex) {
        if (vertex == null) {
            return;
        }

        Iterator<Edge> i = edges.iterator();
        while (i.hasNext()) {
            Edge e = i.next();
            if (e.getV1() == vertex || e.getV2() == vertex) {
                i.remove();
            }
        }

        vertices.remove(vertex);
        clearShortestPathMarking();
    }

    /**
     * Ištrinama pasirinkta briauna.
     */
    public void removeSelectedEdge() {
        removeEdge(selectedEdge);
        selectedEdge = null;
    }

    /**
     * Ištrinama nurodyta briauna.
     * @param edge briauna
     */
    private void removeEdge(Edge edge) {
        edges.remove(edge);
        clearShortestPathMarking();
    }

    /**
     * Sujungti dvi viršūnes briauna.
     * @param v1 pirmoji viršūnė
     * @param v2 antroji viršūnė
     */
    public void connectVertices(Vertex v1, Vertex v2) {
        Edge newEdge = new Edge(v1, v2);
        if (!edges.contains(newEdge) && !v1.equals(v2)) {
            edges.add(newEdge);
        }
    }

    /**
     * Gaunami viršūnės kaimynai.
     * @param vertex viršūnė
     * @param unvisitedVertices neaplankytos viršūnės
     * @return
     */
    private List<Vertex> getNeighbors(Vertex vertex, List<Vertex> unvisitedVertices) {
        List<Vertex> neighbors = new ArrayList<Vertex>();
        for (Edge edge : edges) {
            if (edge.getV1() == vertex) {
                if (unvisitedVertices.contains(edge.getV2())) {
                    neighbors.add(edge.getV2());
                }
            }
            if (edge.getV2() == vertex) {
                if (unvisitedVertices.contains(edge.getV1())) {
                    neighbors.add(edge.getV1());
                }
            }
        }
        return neighbors;
    }

    /**
     * Gaunama egzistuojanti briauna tarp viršūnių.
     * @param v1 pirmoji viršūnė
     * @param v2 antroji viršūnė
     * @return
     */
    private Edge getEdgeBetweenVertices(Vertex v1, Vertex v2) {
        for (Edge edge : edges) {
            if ((edge.getV1() == v1 && edge.getV2() == v2) || (edge.getV2() == v1 && edge.getV1() == v2)) {
                return edge;
            }
        }
        return null;
    }

    /**
     * Gaunama viršūnė su trumpiausiu laikinu atstumu (naudojama skaičiavimui).
     * @param vertices visos viršūnės tarp kurių ieškoti
     * @return
     */
    private Vertex getVertexWithSmallestTentativeDistance(List<Vertex> vertices) {
        Vertex smallestDistanceVerticle = new Vertex(-1, -1);
        smallestDistanceVerticle.setTentativeDistance(Float.MAX_VALUE);

        for (Vertex verticle : vertices) {
            if (verticle.getTentativeDistance() < smallestDistanceVerticle.getTentativeDistance()) {
                smallestDistanceVerticle = verticle;
            }
        }

        return smallestDistanceVerticle;
    }

    /**
     * Randamas greičiausias kelias.
     */
    public void findShortestPath() {
        if (vertices.size() <= 1 || startingVertex == null || destinationVertex == null) {
            return;
        }
        predecessors = new HashMap<Vertex, Vertex>();

        // 1
        for (Vertex vertex : vertices) {
            vertex.setTentativeDistance(Float.MAX_VALUE);
            if (vertex == startingVertex) {
                vertex.setTentativeDistance(0);
            }
        }

        // 2
        for (Vertex verticle : vertices) {
            verticle.setVisited(false);
        }
        Vertex current = startingVertex;
        List<Vertex> unvisitedVerticles = new ArrayList<Vertex>(vertices);

        traverse(unvisitedVerticles, current);

        markShortestPath(destinationVertex);
    }

    /**
     * Vykdomas greičiausio kelio radimas aplankant visas neaplankytas viršūnes.
     * @param unvisitedVertices neaplankytos viršūnės
     * @param current einamoji viršūnė
     */
    private void traverse(List<Vertex> unvisitedVertices, Vertex current) {
        // 3
        List<Vertex> neighbors = getNeighbors(current, unvisitedVertices);
        for (Vertex neighbor : neighbors) {
            Edge edge = getEdgeBetweenVertices(current, neighbor);

            float weight = current.getTentativeDistance() + edge.getWeight();
            if (weight < neighbor.getTentativeDistance()) {
                neighbor.setTentativeDistance(weight);
                predecessors.put(neighbor, current);
            }
        }

        // 4
        current.setVisited(true);
        unvisitedVertices.remove(current);

        // 5
        Vertex smallestDistanceVerticle = getVertexWithSmallestTentativeDistance(unvisitedVertices);
        if (destinationVertex.isVisited() || smallestDistanceVerticle.getTentativeDistance() == Float.MAX_VALUE) {
            return;
        }

        // 6
        current = smallestDistanceVerticle;
        traverse(unvisitedVertices, current);
    }

    /**
     * Trumpiausias kelias pažymimas kita spalva.
     * @param destination tikslas
     */
    private void markShortestPath(Vertex destination) {
        clearShortestPathMarking();
        List<Vertex> nodes = getPath(destination);
        if (nodes.isEmpty() | destination.getTentativeDistance() == Float.MAX_VALUE) {
            return;
        }
        Vertex previous = nodes.get(0);
        for (Vertex current : nodes) {
            if (current == nodes.get(0)) {
                continue;
            }
            Edge edge = getEdgeBetweenVertices(current, previous);
            if (edge != null) {
                edge.setInShortestPath(true);
            }
            previous = current;
        }
    }

    /**
     * Ištrinamas trumpiausio kelio žymėjimas.
     */
    private void clearShortestPathMarking() {
        for (Edge edge : edges) {
            edge.setInShortestPath(false);
        }
    }

    /**
     * Gaunamas kelias iki nurodytos viršūnės.
     * @param target viršūnė
     * @return
     */
    private List<Vertex> getPath(Vertex target) {
        List<Vertex> path = new ArrayList<Vertex>();
        Vertex step = target;
        if (predecessors.get(step) == null) {
            return path;
        }
        path.add(step);
        while (predecessors.get(step) != null) {
            step = predecessors.get(step);
            path.add(step);
        }
        return path;
    }

    public void connectAllVertices() {
        for (Vertex v1 : vertices) {
            for (Vertex v2 : vertices) {
                Edge newEdge = new Edge(v1, v2);
                if (!edges.contains(newEdge) && !v1.equals(v2)) {
                    edges.add(newEdge);
                }
            }
        }
    }

    public void connectVerticesByOrder() {
        Iterator<Vertex> i = vertices.iterator();
        Vertex v1 = null;
        Vertex v2;
        if (i.hasNext()) {
            v1 = i.next();
        }
        while (i.hasNext()) {
            if (i.hasNext()) {
                v2 = i.next();
                Edge newEdge = new Edge(v1, v2);
                if (!edges.contains(newEdge) && !v1.equals(v2)) {
                    edges.add(newEdge);
                }
                v1 = v2;
            }
        }
    }

    public void guessRoute() {
        if (vertices.size() > 1) {
            setStartingVertex(vertices.get(0));
            setDestinationVertex(vertices.get(vertices.size() - 1));
        }
    }

    public List<Vertex> getVertices() {
        return vertices;
    }

    public void setVertices(List<Vertex> verticles) {
        this.vertices = verticles;
    }

    public List<Edge> getEdges() {
        return edges;
    }

    public void setEdges(List<Edge> edges) {
        this.edges = edges;
    }

    public Vertex getStartingVertex() {
        return startingVertex;
    }

    public void setStartingVertex(Vertex startingVerticle) {
        this.startingVertex = startingVerticle;
        setSelectedVertex(null);
        clearShortestPathMarking();
    }

    public Vertex getDestinationVertex() {
        return destinationVertex;
    }

    public void setDestinationVertex(Vertex destinationVertex) {
        this.destinationVertex = destinationVertex;
        setSelectedVertex(null);
        clearShortestPathMarking();
    }

    public Vertex getSelectedVertex() {
        return selectedVertex;
    }

    public void setSelectedVertex(Vertex selectedVertex) {
        this.selectedVertex = selectedVertex;
    }

    public Edge getSelectedEdge() {
        return selectedEdge;
    }

    public void setSelectedEdge(Edge selectedEdge) {
        this.selectedEdge = selectedEdge;
    }

}
